package Sort;

import java.lang.reflect.Array;
import java.nio.channels.SelectionKey;
import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}19:35
 */
public class TestSort {
    public static void BubbleSort(int[] arr){
        if(arr.length == 0){
            return;
        }
        int temp = 0;
        boolean flag = false;
        for(int i = 0; i < arr.length; i++){// 有n趟
            for(int j = 1; j < arr.length; j++){// 每一趟的具体内容
                if(arr[j - 1] > arr[j]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
            if (!flag){
               break;
            }
            flag = false;
        }
    }

    public static void SelectSort(int[] arr){
        if(arr.length == 0){
            return;
        }
        for(int i = 0; i < arr.length; i++){
            int min = arr[i];
            int index = i;
            for(int j = i + 1; j < arr.length;j++){
                if(arr[j] < min){
                    index = j;
                    min = arr[j];
                }
            }
            if(arr[i] != min){
                arr[index] = arr[i];
                arr[i] = min;
            }
        }
    }

    public static void InsertSort(int[] arr){
        if (arr.length == 0){
            return;
        }

        for (int i = 1; i < arr.length; i++){
            int indexValue = arr[i];
            int index = i - 1;
            while (index >= 0 && arr[index] > indexValue){
                arr[index + 1] = arr[index];
                index--;
            }

            if (arr[index + 1] != indexValue){
                arr[index + 1] = indexValue;
            }
        }
    }

    public static void ShellSort(int[] arr){
        if(arr.length == 0){
            return;
        }
        int len = arr.length;
        for(int gap = len / 2; gap > 0; gap/=2){
            for(int i = gap; i < arr.length; i++){// 开始插入排序
                int indexValue = arr[i];

                int index = i - gap;
                while(index >= 0 && arr[index] > indexValue){
                    arr[index + gap] = arr[index];
                    index -= gap;
                }
                if(index != i + gap){
                    arr[index + gap] = indexValue;
                }
            }
        }

    }

    public static void 	qucikSort(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        int l = left;
        int r = right;
        int indexValue = arr[l];
        while(l < r){
            // 一定要先判断右边，因为倒序先左边会 出BUG会直接让l == r无法继续之后的判断
            while(l < r && arr[r] >= indexValue){
                r--;
            }
            while(l < r && arr[l] <= indexValue){
                l++;
            }
            if(l != r){
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        arr[left]  = arr[l];
        arr[l] = indexValue;
        qucikSort(arr,left,l - 1);
        qucikSort(arr,l + 1,right);
    }

    //归并排序
    public static void merge(int[] arr,int left,int right,int mid,int[] temp){
        int l = left;
        int r = mid + 1;
        int index = 0;

        while(l <= mid && r <= right){
            if(arr[l] <= arr[r]){
                temp[index++] = arr[l++];
            }else{
                temp[index++] = arr[r++];
            }
        }

        // 将剩余的都填充到temp数组中
        while(l <= mid){
            temp[index++] = arr[l++];
        }

        while(r <= right){
            temp[index++] = arr[r++];
        }

        //复制到arr中
        index = 0;
        int leftIndex = left;
        while(leftIndex <= right){
            arr[leftIndex++] = temp[index++];
        }
    }

    // 进行分
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(arr,left,mid ,temp);
            mergeSort(arr,mid + 1,right,temp);
            merge(arr,left,right,mid,temp);
        }
    }

    // 堆排序
    // 首先写好堆顶化的代码
    public static void heapfiy(int[] arr,int i,int n){
        if(i >= n){
            return;
        }
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int maxIndex = i;
        if(left < n && arr[left] > arr[maxIndex]){
            maxIndex = left;
        }
        if(right < n && arr[right] > arr[maxIndex]){
            maxIndex = right;
        }

        if(maxIndex != i){		// 说明发生了交换
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
            heapfiy(arr,maxIndex,n);
        }
    }

    // 因为如果从头遍历的话，如果子节点以下没有堆顶化会产生错误的结果
    public static void heapfiy_bulid(int[] arr){
        int lastChildIndex = arr.length;
        int lastParent = (lastChildIndex - 1) / 2;
        for(int i = lastParent; i >= 0; i--){
            heapfiy(arr,i,arr.length);
        }
    }

    // 进行排序
    public static void heap_sort(int[] arr,int n){
        heapfiy_bulid(arr);//进行第一次的堆顶堆顶化 此时arr[0]；已经是最大的了
        for(int i = n-1; i >= 0; i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapfiy(arr,0,i); // 将最后一个数剔除 进行下一轮的堆顶化
        }
    }

    public static void main(String[] args) {
        int[] arr = {8,7,6,5,4,3,2,1};
//        merget(arr,0,arr.length-1,temp);
//        insertSort(arr);
//        quickSort(arr,0,arr.length - 1);
//        shellSort(arr);

//        BubbleSort(arr);
//        SelectSort(arr);
//        InsertSort(arr);
//        ShellSort(arr);
//        qucikSort(arr,0,arr.length - 1);
        heap_sort(arr,arr.length);
//        mergeSort(arr,0,arr.length - 1,new int[arr.length]);
        System.out.println(Runtime.getRuntime().availableProcessors());
        System.out.println(Arrays.toString(arr));
    }
}
